#include<iostream>
#include<iomanip>
#include<stdio.h>
using namespace std;
#define BLACK 0
#define RED 1
 
typedef struct interval{
	double low;
	double high;
	}interval;
 
typedef struct IntervalTNode{
	double key;
	bool color;
	IntervalTNode *parent;
	IntervalTNode *left;
	IntervalTNode *right;
 
	interval inte;  //additional information
	double max;        //additional information
 
	}IntervalTNode;
 
typedef struct IntervalTree{
	IntervalTNode *root;
	}IntervalTree;
 
//init sentine NIL
interval interval0={-1,-1};
IntervalTNode NILL={-1,BLACK,NULL,NULL,NULL,interval0,-1};
IntervalTNode *NIL=&NILL;          
 
int Max(double a,double b,double c)
{
	if(a>b)
		return a>c ? a:c;
	else
		return b>c ? b:c;
	}
bool Overlap(interval a,interval b)
{
	if(a.high < b.low || a.low > b.high)     // a & b do not overlap
		return 0;
	return 1;
	}
IntervalTNode *IntervalT_Search(IntervalTree *T,interval i)
{
	IntervalTNode *x=T->root;
	while(x!=NIL && !Overlap(i,x->inte))
	{ 
		if(x->left !=NIL && x->left->max>= i.low)
			x=x->left;
		else
			x=x->right;
		}
	return x;
}
 
 
void IntervalT_InorderWalk(IntervalTNode *x)    //以Low作为key值实现中序遍历的输出 ,同时输出该节点颜色和扩展信息max 
{
	if(x!=NIL)  
 	 {  
		IntervalT_InorderWalk(x->left);
		printf("[%5.2f  %5.2f]\n",x->inte.low,x->inte.high);
		if(x->color==1)
			cout<<"     Red       "<<x->max<<endl;
		else
			cout<<"     Black     "<<x->max<<endl;
 
		IntervalT_InorderWalk(x->right);
 		} 
 
	}
 
IntervalTNode *IntervalT_Minimum(IntervalTNode *x)  //返回最小节点 
{
	while(x->left != NIL)
		x=x->left;
	return x;
	}
 
IntervalTNode *IntervalT_Successor(IntervalTNode *x) //返回该节点的后继 
{
     if(x->right != NIL)
         return IntervalT_Minimum(x->right);
     IntervalTNode *y = x->parent;
      while(y != NIL && x  == y->right){
         x = y;
         y = y->parent;
	    }
     return y;
	}
 
void Left_Rotate(IntervalTree *T,IntervalTNode *x) // 左旋操作 
{
	IntervalTNode *y=x->right;    //set y
 
	x->right=y->left;       //turn y's left subtree into x's right subtree
	if(y->left!=NIL)
		y->left->parent=x;
 
	y->parent=x->parent;     //link x's parent to y;
	if(x->parent == NIL)
		T->root=y;
	else if(x==x->parent->left)
		x->parent->left=y;
	else
		x->parent->right=y;
 
	y->left=x;               //put x on y's left
	x->parent=y;
	
	//maitaining additional information
	y->max=x->max;
	x->max=Max(x->inte.high,x->left->max,x->right->max);
	}
 
void Right_Rotate(IntervalTree *T,IntervalTNode *x) //右旋操作 
{
	IntervalTNode *y=x->left;      //set y
	
	x->left=y->right;   //link x's left tree into y's right subtree;
	if(y->right !=NIL)
		y->right->parent=x;
	
	y->parent=x->parent;    //link x's parent to y
	if(x->parent == NIL)
		T->root=y;
	else if(x == x->parent->left)
		x->parent->left=y;
	else
		x->parent->right=y;
	
	y->right=x;         //put x on y's right
	x->parent=y;
 
	//Maintaining additional information
	y->max=x->max;
	x->max=Max(x->inte.high,x->left->max,x->right->max);
 
	}
void IntervalT_InsertFixup(IntervalTree *T,IntervalTNode *z)  //在插入后维持原有红黑树的基本性质 
{
	while(z->parent->color==RED)
	{
		if(z->parent == z->parent->parent->left)    
		{
			IntervalTNode *y=z->parent->parent->right;   
			if(y->color==RED)
			{  
				z->parent->color=BLACK;            //case 1
				y->color=BLACK;                    //case 1
				z->parent->parent->color=RED;      //case 1
				z=z->parent->parent;               //case 1
				}
			else
			{
			   	if(z==z->parent->right)
				{ 
					z=z->parent;                    //case 2
					Left_Rotate(T,z);               //case 2
				 	}
				z->parent->color=BLACK;             //case 3
				z->parent->parent->color=RED;       //case 3
				Right_Rotate(T,z->parent->parent);  //case 3
		 		} 
		 	}
		else
		{//a me as then clause with "right" and "left" exchanged  
			IntervalTNode *y=z->parent->parent->left;
			if(y->color==RED)
			{
				z->parent->color==BLACK;
				y->color=BLACK;
				z->parent->parent->color=RED;
				z=z->parent->parent;
		 	 	}
			else
			{
				if(z==z->parent->left)
				{
					z=z->parent;
					Right_Rotate(T,z);
			 	 	}
				z->parent->color=BLACK;
				z->parent->parent->color=RED;
				Left_Rotate(T,z->parent->parent);
			  	} 
			} 
		}   
	T->root->color=BLACK;      //turn the root to BLACK
	}
void IntervalT_Insert(IntervalTree *T,interval inte)  //插入区间 以形成区间树 
{
	IntervalTNode *z=new IntervalTNode();
	z->key=inte.low;
	z->max=inte.high;
	z->inte=inte;
	z->color =RED;   
	z->parent=NIL;
	z->left=NIL;
	z->right=NIL;
 
	IntervalTNode *y=NIL;        //y is the parent of x
	IntervalTNode *x=T->root;
	while(x != NIL)
	{ 
		x->max=max(x->max,z->max);     //Maintaining the max value of each node from z up to root
		y=x;
		if(z->key < x->key)
			x=x->left;
		else
			x=x->right;
		}   
	z->parent=y;   //link new node's parent node to y(y's child is NIL)
	if(y==NIL)
		T->root=z;
	else if(z->key < y->key)
		y->left=z;
	else
		y->right =z;
	IntervalT_InsertFixup(T,z);
	}
	